package leetcode_core.leetcode_4;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月21日 15:18
 */
public class SoupServings {
    public double soupServings(int n) {
        n = (int)Math.ceil((double) n/25.0);
        //有n份汤
        if(n>=179){
            return 1.0;
        }
        double[][] dp = new double[n+1][n+1];
        //base-case
        //当A有0份汤,而B有0份汤的时候,由于这时候永远不可能A比B先分完
        dp[0][0] = 0 + 1*0.5;
        //当A有i份汤,而B有0份汤的时候,汤A永远不可能比B先分完,而且A和B不可能同时分完
        for(int i = 1 ;i<=n;i++){
            dp[i][0] = 0;
        }
        //当A有0份汤,而B有i份汤的时候,汤A比B先分完,概率是1,而且A和B不可能同时分完
        for(int i = 1;i<=n;i++){
            dp[0][i] = 1.0;
        }
        //然后对于A有i份汤,B有j份汤的时候...
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = 0.25*(dp[Math.max(0,i-4)][j]+
                                 dp[Math.max(0,i-3)][Math.max(0,j-1)]+
                                 dp[Math.max(0,i-2)][Math.max(0,j-2)]+
                                 dp[Math.max(0,i-1)][Math.max(0,j-3)]);
            }
        }
        return dp[n][n];
    }
}
